package org.totoro.structure.list.impl;


import org.totoro.structure.list.List;

import java.util.Arrays;
import java.util.Objects;

/**
 * 动态数量
 *
 * @author daocr
 * @date 2020/3/22
 */
public class ArrayList<E> implements List<E> {

    /**
     * 空数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 数据存储
     */
    private Object[] elementData;
    /**
     * 总大小
     */
    private int size;

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 传入初始大小
     *
     * @param initialCapacity
     */
    public ArrayList(Integer initialCapacity) {

        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " +
                    initialCapacity);
        }

    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean contains(E o) {
        return indexOf(o) != -1;
    }

    @Override
    public boolean add(E e) {

        grow(calculateCapacity(elementData, size + 1));

        elementData[size++] = e;

        return true;
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    /**
     * 扩容
     *
     * @param minCapacity
     */
    private void grow(int minCapacity) {

        int oldCapacity = elementData.length;
        // 判断空间是否够用
        if (minCapacity - oldCapacity < 0) {
            return;
        }

        // 每次扩容之前容量的百分之50
        int newCapacity = oldCapacity + (oldCapacity >> 1);

        // 取最大值
        newCapacity = Math.max(minCapacity, newCapacity);

        // 超过最大容量
        if (newCapacity < 0) {
            throw new OutOfMemoryError();
        }
        // 申请数组
        elementData = Arrays.copyOf(elementData, newCapacity);

    }


    @Override
    public void add(int index, E element) {

        outOfBound(index);

        grow(calculateCapacity(elementData, size + 1));

        //  index 位置的数据整体，往后移动一格
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);

        // 覆盖数据
        elementData[index] = element;
        size++;

    }

    private void outOfBound(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index:" + index);
        }
    }

    @Override
    public int indexOf(E o) {

        for (int i = 0; i < elementData.length; i++) {
            if (Objects.equals(elementData[i], o)) {
                return i;
            }
        }

        return -1;
    }

    @Override
    public int lastIndexOf(E o) {
        for (int i = elementData.length - 1; i > 0; i--) {
            if (Objects.equals(elementData[i], o)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public boolean remove(E o) {

        int index = indexOf(o);

        // 计算 对象后面还有多少元素
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            // 数据往前移动一位
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        }

        // 因为数据往前移动一位，所以最后一个空出来， 删除引用，为了gc 可以回收数据
        elementData[size == 0 ? 0 : size--] = null;

        return true;
    }

    @Override
    public E get(int index) {
        outOfBound(index);

        return (E) elementData[index];
    }

    @Override
    public E getLast() {

        if (isEmpty()) {
            return null;
        }

        return get(size - 1);
    }

    @Override
    public void addLast(E element) {
        add(size, element);
    }

    public static void main(String[] args) {

        ArrayList<String> stringArrayList = new ArrayList<>();

        for (int i = 0; i < 100; i++) {
            stringArrayList.add(String.valueOf(i));
        }

        print(stringArrayList);
        stringArrayList.remove("2");
        print(stringArrayList);
    }

    private static void print(ArrayList<String> stringArrayList) {
        int size = stringArrayList.size();

        for (int i = 0; i < size; i++) {
            System.out.print(stringArrayList.get(i));
        }

        System.out.println();
    }
}
